//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Core.h".
//-------------------------------------------------------------------

#ifndef _UXS_CIRCULAR_QUEUE_H
#define _UXS_CIRCULAR_QUEUE_H

#pragma once

#include "TArray.h"

namespace UX_STL
{
namespace UXTypes
{

	//
	// Circular Queue
	//
	
	#define TCircularQueue		circular_queue

	template <	typename T,
				typename S = TCopyStrategy<T>,
				typename A = TAllocator<T>
			 >
	struct TCircularQueue
	{
	// types
	public:
		typedef TMemoryViewer<T>		vis_mem_t;
		typedef S						Strategy;
		typedef A						Allocator;
		typedef T						value_t;
		typedef TCircularQueue<T,S,A>	Self;
		typedef uni_array<T>			uni_arr;
		typedef uni_array<const T>		uni_c_arr;


	// variables
	private:
		union {
			T		*	_pMemory;
			vis_mem_t	_pVisible;
		};
		usize			_uFirst,
						_uEnd,		// last + 1
						_uSize;
		
		//  _____________ __________ _____________
		// | used memory | reserved | used memory |
		// 0          _uEnd      _uFirst       _uSize


	// methods
	private:
		void  _Reallocate (usize uNewSize, bool bReserve);
		usize _WrapIndex (isize i) const;

		template <typename B>
		void _AppendFront (B* pArray, usize uCount);
		
		template <typename B>
		void _AppendBack (B* pArray, usize uCount);

		static usize _GetNewSize (usize uNewSize);


	public:
		TCircularQueue ();
		
		TCircularQueue (const Self &other);

		RVALUE_REFERENCE_ONLY( TCircularQueue (Self &&other); )

		~TCircularQueue ();
		
		T		&	Front ();
		T const	&	Front () const;

		T		&	Back ();
		T const	&	Back () const;

		bool		operator ! () const					{ return not Empty(); }
		
		T		&	operator [] (usize i);
		T const	&	operator [] (usize i) const;
		
		void PushBack (const T &tValue);
		void PushBack (INOUT T& tValue);
		RVALUE_REFERENCE_ONLY( void PushBack (T&& tValue); )

		void PushFront (const T &tValue);
		void PushFront (INOUT T& tValue);
		RVALUE_REFERENCE_ONLY( void PushFront (T&& tValue); )
		
		void PopBack ();
		void PopFront ();
		
		void AppendFront (uni_c_arr sArray);
		void AppendFront (uni_arr sArray);
		void AppendFront (const Self &sQueue);
		void AppendFront (INOUT Self &sQueue);

		void AppendBack (uni_c_arr sArray);
		void AppendBack (uni_arr sArray);
		void AppendBack (const Self &sQueue);
		void AppendBack (INOUT Self &sQueue);
		
		void Reserve (usize uSize);

		void Copy (const Self &other);

		void Clear ();
		void ClearMem ();
		
		void GetParts (OUT uni_arr &part0, OUT uni_arr &part1);
		void GetParts (OUT uni_c_arr &part0, OUT uni_c_arr &part1) const;

		usize		Count ()	 const;
		usize		Size ()		 const				{ return sizeof(T) * Count(); }
		usize		Capacity ()	 const				{ return _uSize-1; }
		usize		FullSize ()	 const				{ return sizeof(T) * Capacity(); }
		bool		Empty ()	 const				{ return _uFirst == _uEnd; }
		usize		LastIndex () const				{ return Count()-1; }
	};


	
	template <typename T, typename S, typename A>
	inline TCircularQueue<T,S,A>::TCircularQueue () :
		_pMemory(null), _uFirst(0), _uEnd(0), _uSize(0)
	{}
	

	template <typename T, typename S, typename A>
	inline TCircularQueue<T,S,A>::TCircularQueue (const Self &other) :
		_pMemory(null), _uFirst(0), _uEnd(0), _uSize(0)
	{
		Copy( other );
	}


	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline TCircularQueue<T,S,A>::TCircularQueue (Self &&other) :
			_pMemory(other._pMemory), _uFirst(other._uFirst), _uEnd(other._uEnd), _uSize(other._uSize)
		{
			other._pMemory	= null;
			other._uFirst = other._uEnd = other._uSize = 0;
		}
	)
	

	template <typename T, typename S, typename A>
	inline TCircularQueue<T,S,A>::~TCircularQueue ()
	{
		Clear();
	}
		
	
	template <typename T, typename S, typename A>
	inline usize TCircularQueue<T,S,A>::_GetNewSize (usize uNewSize)
	{
		const usize	nom		 = CoreTypesConfig::CircularQueueResizingNominator;
		const usize	den		 = CoreTypesConfig::CircularQueueResizingDenominator;
		const usize	min_size = CoreTypesConfig::CircularQueueResizingMinSize;
		const usize	temp	 = (uNewSize * nom + den - 1) / den;
		return ( uNewSize + (temp < min_size ? min_size : temp) );
	}


	template <typename T, typename S, typename A>
	inline void  TCircularQueue<T,S,A>::_Reallocate (usize uNewSize, bool bReserve)
	{
		if ( uNewSize <= _uSize )
			return;
		
		// save old values
		usize	u_size	= _uSize;
		usize	u_count	= Count();
		T	*	p_mem	= _pMemory;

		_uSize			= bReserve ? _GetNewSize(uNewSize) : uNewSize;
		_pMemory		= Allocator::Allocate( _uSize );

		if ( p_mem == null )
		{
			_uFirst = _uEnd = 0;
			return;
		}

		// replace
		if ( Empty() )
		{}
		else
		if ( _uFirst > _uEnd )
		{
			usize	u_off = u_size - _uFirst;
			Strategy::Replace( _pMemory, p_mem + _uFirst, u_off );
			Strategy::Replace( _pMemory + u_off, p_mem, _uEnd );
		}
		else
		{
			Strategy::Replace( _pMemory, p_mem + _uFirst, _uEnd - _uFirst );
		}
		
		_uFirst = 0;
		_uEnd   = u_count;

		Allocator::Deallocate( p_mem );
	}

	
	template <typename T, typename S, typename A>
	inline usize TCircularQueue<T,S,A>::_WrapIndex (isize i) const
	{
		return ( i < 0 ? _uSize + i : ( i >= (isize)_uSize ? i - _uSize : i ) );
	}
	

	template <typename T, typename S, typename A>
	inline usize  TCircularQueue<T,S,A>::Count () const
	{
		return	_uFirst <= _uEnd ?
				( _uEnd - _uFirst ) :
				( _uSize - _uFirst + _uEnd );
	}

	
	template <typename T, typename S, typename A>
	inline T & TCircularQueue<T,S,A>::Front ()
	{
		ASSERT( not Empty() );
		return _pMemory[ _uFirst ];
	}
	

	template <typename T, typename S, typename A>
	inline T const & TCircularQueue<T,S,A>::Front () const
	{
		ASSERT( not Empty() );
		return _pMemory[ _uFirst ];
	}

	
	template <typename T, typename S, typename A>
	inline T & TCircularQueue<T,S,A>::Back ()
	{
		ASSERT( not Empty() );
		return _pMemory[ _WrapIndex( _uEnd - 1 ) ];
	}

	
	template <typename T, typename S, typename A>
	inline T const & TCircularQueue<T,S,A>::Back () const
	{
		ASSERT( not Empty() );
		return _pMemory[ _WrapIndex( _uEnd - 1 ) ];
	}
		
	
	template <typename T, typename S, typename A>
	inline T & TCircularQueue<T,S,A>::operator [] (usize i)
	{
		ASSERT( i < Count() );
		return _pMemory[ _WrapIndex( i + _uFirst ) ];
	}

	
	template <typename T, typename S, typename A>
	inline T const & TCircularQueue<T,S,A>::operator [] (usize i) const
	{
		ASSERT( i < Count() );
		return _pMemory[ _WrapIndex( i + _uFirst ) ];
	}
		
	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::PushBack (const T &tValue)
	{
		usize cnt = Count();

		if ( cnt+2 >= _uSize )
			_Reallocate( _uSize+1, true );
		
		Strategy::Construct( _pMemory + _uEnd, tValue );
		_uEnd = _WrapIndex( _uEnd + 1 );
	}

	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::PushBack (T& tValue)
	{
		if ( Count()+2 >= _uSize )
			_Reallocate( _uSize+1, true );
		
		Strategy::Construct( _pMemory + _uEnd, tValue );
		_uEnd = _WrapIndex( _uEnd + 1 );
	}

	
	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline void TCircularQueue<T,S,A>::PushBack (T&& tValue)
		{
			if ( Count()+2 >= _uSize )
				_Reallocate( _uSize+1, true );
		
			Strategy::Construct( _pMemory + _uEnd, ToRValueRef( tValue ) );
			_uEnd = _WrapIndex( _uEnd + 1 );
		}
	)
	

	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::PushFront (const T &tValue)
	{
		if ( Count()+2 >= _uSize )
			_Reallocate( _uSize+1, true );
		
		_uFirst = _WrapIndex( _uFirst - 1 );
		Strategy::Construct( _pMemory + _uFirst, tValue );
	}

	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::PushFront (T& tValue)
	{
		if ( Count()+2 >= _uSize )
			_Reallocate( _uSize+1, true );

		_uFirst = _WrapIndex( _uFirst - 1 );
		Strategy::Construct( _pMemory + _uFirst, tValue );
	}


	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline void TCircularQueue<T,S,A>::PushFront (T&& tValue)
		{
			if ( Count()+2 >= _uSize )
				_Reallocate( _uSize+1, true );

			_uFirst = _WrapIndex( _uFirst - 1 );
			Strategy::Construct( _pMemory + _uFirst, ToRValueRef( tValue ) );
		}
	)
		
	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::PopBack ()
	{
		if ( not Empty() )
		{
			_uEnd = _WrapIndex( _uEnd - 1 );
			Strategy::Destruct( _pMemory + _uEnd );
		}
	}

	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::PopFront ()
	{
		if ( not Empty() )
		{
			Strategy::Destruct( _pMemory + _uFirst );
			_uFirst = _WrapIndex( _uFirst + 1 );
		}
	}

		
	template <typename T, typename S, typename A>
	template <typename B>
	inline void TCircularQueue<T,S,A>::_AppendFront (B *pArray, usize uCount)
	{
		if ( uCount == 0 )
			return;

		if ( Count() + uCount + 1 >= _uSize )
			_Reallocate( _uSize + uCount + 1, true );

		if ( Empty() )
		{
			Strategy::Copy( _pMemory, pArray, uCount );
			_uFirst = 0;
			_uEnd   = uCount;
		}
		else
		if ( _uFirst < _uEnd )
		{
			usize	count = UXMath::Min( uCount, _uFirst );

			Strategy::Copy( _pMemory + _uFirst - count, pArray + uCount - count, count );
			_uFirst -= count;
			
			if ( count != uCount )
			{
				count   = uCount - count;
				_uFirst = _uSize - count;
				Strategy::Copy( _pMemory + _uFirst, pArray, count );
			}
		}
		else
		{
			Strategy::Copy( _pMemory + _uFirst - uCount, pArray, uCount );
			_uFirst -= uCount;
		}
	}

	
	template <typename T, typename S, typename A>
	template <typename B>
	inline void TCircularQueue<T,S,A>::_AppendBack (B *pArray, usize uCount)
	{
		if ( uCount == 0 )
			return;

		if ( Count() + uCount + 1 >= _uSize )
			_Reallocate( _uSize + uCount + 1, true );

		if ( Empty() )
		{
			Strategy::Copy( _pMemory, pArray, uCount );
			_uFirst = 0;
			_uEnd   = uCount;
		}
		else
		if ( _uFirst < _uEnd )
		{
			usize	count = UXMath::Min( uCount, _uSize - _uEnd );

			Strategy::Copy( _pMemory + _uEnd, pArray, count );
			_uEnd += count;
			
			if ( count != uCount )
			{
				_uEnd = uCount - count;
				Strategy::Copy( _pMemory, pArray + count, uCount - count );
			}
		}
		else
		{
			Strategy::Copy( _pMemory + _uEnd, pArray, uCount );
			_uEnd += uCount;
		}
	}
	
	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendFront (uni_c_arr sArray)
	{
		if ( sArray.Empty() )	return;
		return _AppendFront<const T>( sArray.ptr(), sArray.Count() );
	}
		

	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendFront (uni_arr sArray)
	{
		if ( sArray.Empty() )	return;
		return _AppendFront<T>( sArray.ptr(), sArray.Count() );
	}
		

	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendFront (const Self &sQueue)
	{
		uni_c_arr	part0;
		uni_c_arr	part1;
		sQueue.GetParts( part0, part1 );

		AppendFront( part1 );
		AppendFront( part0 );
	}


	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendFront (INOUT Self &sQueue)
	{
		uni_arr		part0;
		uni_arr		part1;
		sQueue.GetParts( part0, part1 );

		AppendFront( part1 );
		AppendFront( part0 );
	}


	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendBack (uni_c_arr sArray)
	{
		if ( sArray.Empty() )	return;
		return _AppendBack<const T>( sArray.ptr(), sArray.Count() );
	}
		
		
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendBack (uni_arr sArray)
	{
		if ( sArray.Empty() )	return;
		return _AppendBack<T>( sArray.ptr(), sArray.Count() );
	}
		
	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendBack (const Self &sQueue)
	{
		uni_c_arr	part0;
		uni_c_arr	part1;
		sQueue.GetParts( part0, part1 );

		AppendBack( part1 );
		AppendBack( part0 );
	}
	

	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::AppendBack (INOUT Self &sQueue)
	{
		uni_arr		part0;
		uni_arr		part1;
		sQueue.GetParts( part0, part1 );

		AppendBack( part1 );
		AppendBack( part0 );
	}
	

	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::Reserve (usize uSize)
	{
		if ( uSize <= _uSize )
			return;

		_Reallocate( uSize, false );
	}

	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::Clear ()
	{
		if ( _pMemory != null )
		{
			if ( Empty() )
			{}
			else
			if ( _uFirst > _uEnd )
			{
				Strategy::Destroy( _pMemory + _uFirst, _uSize );
				Strategy::Destroy( _pMemory, _uEnd );
			}
			else
			{
				Strategy::Destroy( _pMemory + _uFirst, Count() );
			}
			Allocator::Deallocate( _pMemory );
		}
		_uFirst = _uEnd = 0;
		_uSize	= 0;
	}

	
	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::ClearMem ()
	{
		if ( _pMemory != null )
		{
			if ( Empty() )
			{}
			else
			if ( _uFirst > _uEnd )
			{
				Strategy::Destroy( _pMemory + _uFirst, _uSize );
				Strategy::Destroy( _pMemory, _uEnd );
			}
			else
			{
				Strategy::Destroy( _pMemory + _uFirst, Count() );
			}
			Strategy::ZeroMem( _pMemory, _uSize );
		}
		_uFirst = _uEnd = 0;
	}
	

	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::Copy (const Self &other)
	{
		ClearMem();
		AppendBack( other );
	}


	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::GetParts (uni_arr &part0, uni_arr &part1)
	{
		if ( Empty() )
		{
			part0 = uni_arr();
			part1 = uni_arr();
		}
		else
		if ( _uFirst > _uEnd )
		{	
			part0 = uni_arr( _pMemory + _uFirst, _uSize - _uFirst );
			part1 = uni_arr( _pMemory, _uEnd );
		}
		else
		{
			part0 = uni_arr( _pMemory + _uFirst, Count() );
			part1 = uni_arr();
		}
	}
	

	template <typename T, typename S, typename A>
	inline void TCircularQueue<T,S,A>::GetParts (uni_c_arr &part0, uni_c_arr &part1) const
	{
		if ( Empty() )
		{
			part0 = uni_c_arr();
			part1 = uni_c_arr();
		}
		else
		if ( _uFirst > _uEnd )
		{	
			part0 = uni_c_arr( _pMemory + _uFirst, _uSize - _uFirst );
			part1 = uni_c_arr( _pMemory, _uEnd );
		}
		else
		{
			part0 = uni_c_arr( _pMemory + _uFirst, Count() );
			part1 = uni_c_arr();
		}
	}

	
	#undef TCircularQueue

}	// UXTypes
}	// UX_STL

#endif	// _UXS_CIRCULAR_QUEUE_H